"""
最长公共子序列
求序列X（长m） 与序列Y（长n）的最长公共子序列
c[i][j]存放长度
b[i][j]标记，用于求解
"""

import numpy as np
import string
import random as rd


def Knapsack(n: int, c, w, v, p, x):
    head = np.zeros([n + 2], dtype=int)
    head[n + 1] = 0
    p[0][0] = 0
    p[0][1] = 0
    left, right, next = 0, 0, 1
    head[n] = 1
    for i in range(n, 0, -1):  # n到1的迭代
        k = left
        for j in range(left, right + 1):
            if p[j][0] + w[i] > c:
                break
            y, m = p[j][0] + w[i], p[j][1] + v[i]
            while k <= right and p[k][0] < y:
                p[next][0] = p[k][0]
                p[next][1] = p[k][1]
                next += 1
                k += 1
            if k <= right and p[k][0] == y:
                if m < p[k][1]:
                    m = p[k][1]
                k += 1
            if m > p[next - 1][1]:
                p[next][0] = y
                p[next][1] = m
                next += 1
            while k <= right and p[k][1] <= p[next - 1][1]:
                k += 1
        while k <= right:
            p[next][0] = p[k][0]
            p[next][1] = p[k][1]
            next += 1
            k += 1
        left = right + 1
        right = next - 1
        head[i - 1] = next
    Traceback(n, w, v, p, head, x)
    # print(p)
    return p[next - 1][1]


def Traceback(n, w, v, p, head, x):
    j, m = p[head[0] - 1][0], p[head[0] - 1][1]
    for i in range(1, n + 1):
        x[i] = 0
        for k in range(head[i + 1], head[i]):
            if p[k][0] + w[i] == j and p[k][1] + v[i] == m:
                x[i] = 1
                j = p[k][0]
                m = p[k][1]
                break


def runKnapsack(n, c, w, v):
    w = [0] + w
    v = [0] + v
    p = np.zeros([pow(2*n, 2), 2], dtype=float)
    x = np.zeros([n + 1], dtype=float)
    maxvalue = Knapsack(n, c, w, v, p, x)
    # print(p)
    return maxvalue, x


def LCSlength(x, y, m, n, b, c):
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if x[i] == y[j]:
                c[i][j] = c[i - 1][j - 1] + 1
                b[i][j] = 1
            else:
                if c[i - 1][j] >= c[i][j - 1]:
                    c[i][j] = c[i - 1][j]
                    b[i][j] = 2
                else:
                    c[i][j] = c[i][j - 1]
                    b[i][j] = 3


# 递归构造最优解
def LCS(x, b, i, j, lcs_str=""):
    if i == 0 or j == 0:
        # 因为前面使用的for是从0开始的，所以这里b[0]也用到了
        return lcs_str
    if b[i][j] == 1:
        lcs_str = x[i] + lcs_str
        return LCS(x, b, i - 1, j - 1, lcs_str)
        # print(x[i], end="")
    if b[i][j] == 2:
        return LCS(x, b, i - 1, j, lcs_str)
    if b[i][j] == 3:
        return LCS(x, b, i, j - 1, lcs_str)


# 迭代构造最优解
def LCS2nd(x, b, i, j):
    lcs_str = ""
    while i > 0 and j > 0:
        if b[i][j] == 1:
            lcs_str = x[i] + lcs_str
            i -= 1
            j -= 1
        if b[i][j] == 2:
            i -= 1
        if b[i][j] == 3:
            j -= 1
    return lcs_str


def runLCS(x: str, y: str):
    m = len(x)
    n = len(y)
    b = np.zeros((m + 1, n + 1), dtype=int)
    c = np.zeros((m + 1, n + 1), dtype=int)
    x = '#' + x
    y = '$' + y
    LCSlength(x, y, m, n, b, c)
    # maxsubstr = LCS(x, b, m, n)
    maxsubstr = LCS2nd(x, b, m, n)
    return int(c[m][n]), maxsubstr


if __name__ == "__main__":
    def test1(x=None, y=None):
        tmp_size = rd.randint(10, 999)
        if x is None:
            x = ''.join(rd.choice(string.ascii_letters + string.digits) for _ in range(tmp_size))
        m = len(x)
        if y is None:
            y = ''.join(rd.choice(string.ascii_letters + string.digits) for _ in range(tmp_size))
        maxlen, maxsubstr = runLCS(x, y)
        print("LCStest\nx串：", x, "\ny串:", y, "\n最长字串的长度：", maxlen, "\n串：", maxsubstr)

    def test2(n=None, c=None, w=None, v=None):
        print("0-1背包问题")
        # n, c = 5, 10
        # w = [0, 2, 2, 6, 5, 4]
        # v = [0, 6, 3, 5, 4, 6]
        if None in [n, c, w, v]:
            tmp_n = rd.randint(4, 20)    # 随机一个物品个数
            tmp_c = rd.randint(10, 100)  # 随机一个背包容量
            tmp_w = [rd.randint(1, tmp_c) for i in range(tmp_n)]
            tmp_v = [rd.randint(1, 1000) for i in range(tmp_n)]
            n, c, w, v = tmp_n, tmp_c, tmp_w, tmp_v

        print("物品个数：", n, "\nb背包容量：", c, "\n 相应重量：", w, "\n价值：", v)
        # p = np.zeros([n*n, 2], dtype=int)
        # x = np.zeros([n + 1], dtype=int)
        maxvalue, x = runKnapsack(n, c, w, v)
        print("最大价值：", maxvalue, "\n背包选择矩阵", x[1:])
        # print(p)

    test1("12345678", "abc234def34568")
    # test2()
